Модели в електронни спортове
Никола Шахпазов
6/5/2021
Въведение
Последното десетилетие, електронните спортове са набрали огромна популярност, особено сред младите. Дори на компютрите за развлечение във ФМИ може да се видят играещи и разгорещено спорещи студенти, а в международен план се провеждат състезания с наградни фондове за десетки милиони. Електронният характер позволява събиране на данни до най-малката детайлност на игрите/играта, както преди самото започване на мачовете, така и от реално време.
В съответната теза ще разгледаме кратко описание на някои известни електронни спортове, подхода при извличане и обработка на данни, както и няколко възможни модела които могат да се приложат за решаването на изхода от мача.
Модели при електронния спорт Dota 2 (Defence of the Ancients 2)
Описание на играта Dota 2
Dota 2 (Защита на Древните) е може би най-популярния електронен спорт, а предшественика му - DОТА е първият такъв.
Двата отбора водят териториална военна битка един с друг, като целта на всеки е да унищожи древните храмове противника си. Освен това, върху картата, двата отбора имат и военни крепости от които на помощ им идват компютърно симулирани войници, чието унищожаване дава злато и точки опит за противниковия отбор.
В една класическа партия участват два отбора, всеки с по пет играча, като всеки играч играе с определен герой.
Броят на героите надвишава 112, като всеки герой има предопределена роля в играта и в този смисъл, правилната комбинация на героите има значителен принос върху вероятността за победа на единия или другия отбор. Героите са предпоределени от ролите за които са подходящи да участват в играта, техни свойства, атрибути и способности.
Свойствата и особеностите на героите, техните способности в битка предоставят голямо разнообразие и различие между героите, давайки на всеки герой негово уникално тактическо предимство за ситуации в играта и различни местоположения по картата. Поради това, за да сформират добър отбор, играчите трябва да са добре запознати със силните и слабите страни на всеки герой.
Съответните роли от които всеки играч може да бъде са
Носач(Carry) - отговорен за носенето на повечето събрано злато от битките с което прави и съотборниците си отговорни за неговото опазване. Докато носачите не участват толкова активно в битките, те трупат злато и опит с който компенсират в късните етапи на играта, където имат далеч повече сила. Името износван идва оттам, че макар и в по-късните етапи на играта да са изключително опасни, в началото на играта са немощни и износвани от своите съотборници.
Подкрепа (Support) - героите с подкрепяща роля са отговорни за опазване на своите съотборници живи, така че да могат да събират спокойно злато и точки опит. Това се случва посредством способности за лекуване и защитни магии които героите с подкрепяща роля имат. Също така се занимават с разузнаване на картата и покупка на боеприпаси. Също така, имат способности като лечение на съотборниците си или зашеметяване на противниците си. За тях златото не е такъв приоритет като за носачите. Често се случва да жертват себе си за спечелят време за бягство от съотборниците си.
Бомбардировач (Nuker) - героите от този тип имат експлозивни магии с много високо ниво на щети и бавно възстановяване. Може да нарани и погуби по няколко вражески героя наведнъж.
Деактиватор (Disabler) - деактиваторите имат способност да зашеметяват вражески герои, както и да спират техни магии и удари.
Джунглър (Jungler) - събират злато и артефакти, повечето случаи в джунглата на картата.
Странично атакуващи (Off-laner) - Това е една от най-застрашените роли в цялата игра. Тяхна отговорност е самостоятелно да обезопасят страничните алеи на играта, с което са под голям риск да бъдат атакувани от няколко противникови героя наведнъж.
Други
Използвани данни за Dota 2 и техните предиктори
Данни за предварителни прогнози
За предварителни прогнози, един набор от данни предоставен от Yang et al.[2] съдържа 78362 игри с 19790 участващи в тях играча с висок рейтинг.
Всеки мач има информация за побежваващия отбор, уникален номер на всеки мач, играчите и избраните герои в съответните мачове. Освен това са събрани хакатеристики и статистики за всеки герой, като способности, силни и слаби страни, препоръчана роля за игра, бързина, сила, интелект и много други.
За играчите имаме исторически статистики като рейтинг оценяващ силата на играча, както и информация за брой победи и загуби с често играни от него герои. Използваните данни са извлечени от сайта http://www.opendota.com.
Подобни данни използваме и от работата на Conley et al. [1], както и от състезание за прогнозиране на Dota 2 игри проведено в сайта http://www.Kaggle.com.
Данни за предварителни прогнози
За данни от реално време, използваме набор от 50 хиляди игри, предоставени от споменатото по-горе състезание в Kaggle.com При него имаме пълна информация за играчите, избраните герои, победителя, както и информация за различни статистики събрани в реално време на интервал от една минута. Някои такива характеристики са
- Събрано злато за всеки играч
- Натрупан опит за всеки играч
- Брой финализиращи удари
- Разрушаване на вражески кули
- Купени артефакти и избрани подобрения при качване на нива опит
- И други
Модели за предварително прогнозиране на победа върху Dota 2 мачове
Една от задачите които представяляват интерес за нас, е да успеем да направим точна прогноза върху изхода от мача, единствено с информация за участващите играчи и избраните от тях герои. В този смисъл, целта е да моделираме изхода от мача като Бернулиева Случайна величина
\[ Y := \begin{cases} 1,& \text{ако отбор Сияние печели } \\ 0 & \text{иначе} \end{cases} \] както и вероятността \(P(Y=1)\).
Логистична регресия
Един подход за прогнозирането на Y който е използван в [1], е чрез метода на Логистичната Регресия. Посредством него, можем да представим логистичната трансформация (свързваща функция) на вероятността за победа на определен мач, спрямо вероятността за загуба като линейна комбинация на това дали определен герой участва в някой от отборите.
\[ log[\frac{P(Y = 1)}{1 - P(Y = 1)}] = \beta_0 + \sum_{i=1}^{113}\beta_i\unicode{x1D7D9}(\text{герой } i \in \text{отбор 1}) + \sum_{i=113}^{226}\beta_i\unicode{x1D7D9}(\text{герой } i-112 \in \text{отбор 2}) = \\ = \beta_0 + <\overrightarrow{\beta},\overrightarrow{X}> \]
където
\[ X_i = \begin{cases} 1,& \text{ако герой i участва в отбор Сияние за i=1,...,113} \\ 1, & \text{ако герой i-112 участва в отбор Мраколес за i=113,...,226} \\ 0 & \text{иначе} \end{cases} \]
Изразявайки спрямо P(Y=1), получаваме
\[ P(Y=1 | \overrightarrow{\beta}) = \frac{1}{1 + e^{-(\beta_0 + \sum_{i=1}^p\beta_ix_i)}} \]
Параметрите \(\beta_0, ...,\beta_{226}\) оценяваме с метода на максимално правдоподобие, при който максимизираме функцията на правдоподобие.
\[ \overrightarrow{\hat{\beta}} = \underset{\overrightarrow{\beta}}{{argmax}}\prod_{i=1}^nP(Y_i=1 | \overrightarrow{\beta}) \]
за определени \(1,...,n\) игри които имаме. За целта, параметрите ги оценяваме върху заделено от нас множество от игри, а проверката за точността на прогнозата я правим върху остатъка (train-test split). Пропорцията която използваме за двете множества е 70% за трениране на модела и 30% за тестване на прогнозата.
За фунцкията на правдоподобие е трудно да се намери аналитично решение и в почето случаи, софтуерните пакети които използваме прилагат числена апроксимация за да намерят параметрите които максимизират функцията.
Оценявайки параметрите и прогнозирайки върху множеството за тестване, Conley at al. [1] са достигнали около 71% оценка за точността върху прогнозата. Извършвайки по детайлно разглеждане на използвните от тях данни, може да се види, че така или иначе, в 60% от случаите, отбор Сияние побеждава и съответната точност не е сравнена с точност от базов модел (benchmark). Същия модел е използван в Yang et al. [2], където авторите са получили 60% оценка за точност на прогнозиране на отбор Сияние.
Получаваме около 60% точност на прогнозата, която можем да сравним с точността на базов модел (**baseline*), който прогнозира победителя като отбора който просто има повече победи и дава 51% точност.
Друг подход използван в Yang et al. [2] е отново с Логистична Регресия, но с далеч повече предиктори за изразяването на отклика Y. Освен използваният 226-мерен вектор с индикатори за играните герои, те са използвали и още няколко групи предиктори, като характеристики на играните герои (hero attributes), като
- базова жизненост
- базова сила
- базова регенерация
- базови умения в стрелба
- други.
Друга група която са добавили е статистики от сайта www.dotabuff.com за това колко победи и загуби имат всеки от играчите с избраните от тях герои.
Като финал, авторите са използвали изчисляван от opendota.com рейтинг на играчите, наричан MMR (Matchmaking Rating) и взето от същия сайт разпределение на съответните MMR оценки и разпределение на 7 специфични статистики за играни герои като
- среден количество натрупан опит на минута (xp_per_min)
- среден брой убийства на минута (kills_per_min)
- средно нанесени щети на минута (hero_damage_per_min)
- среден нанесени финализиращи удари на минута (last_hits_per_min)
- лекуване на съотборници (hero_healing_per_min)
- брой потрошени вражески кули (tower_damage)
- средно количество злато събирано на минута (gold_per_min)
Посредством рейтинга на играча, разпределението на рейтинга и разпределенията на гореописаните статистики, авторите взимат процентила в който попада рейтинга на всеки играч, и в същия процентил взимат стойността на всяка от статистиките по-горе.
Комбинирайки всички тези предиктори във един 611-мерен вектор от предиктори, авторите твърдят за достигане на 71% точност. Едно по-детайлно разглеждане на ефекта върху точността на всяка група предиктори, стигнахме до съответните количества.
| Група Предиктори | Точност |
|---|---|
| Избрани Герои | 59% |
| Характеристики на Героите | 55.67% |
| Честота на победи с Герой | 54% |
| MMR рейтинги | 55% |
| Трансформация върху MMR | 54.35% |
| Честота на победа на играч с герой | 69.72% |
| Избрани герои + Честота на победи | 70.37% |
| Избрани герои + Честота на победи + Трансформация | 70.58% |
Виждаме, че предложената трансформация, всъщност е сред най слабата група предиктори - оценката за точността е около 54%, докато най-силна е групата от честотата на победи на играч с герой. 611-мерния вектор спокойно може да се сбие до група от 10 предиктора и това малко да промени или намали точността на модела.
Основен проблем на този подход е, че честотата на победи на определен играч с определен герой, не е съпоставена с определен мач (няма времеви компонент), а е взета в момента на извличане на всички данни, тоест след самите мачове. Това създава предпоставка за теч на информация/данни (Data Leakage) и надвишена прогноза за точността на модела, поради използването на предиктори от бъдещето.
Друг проблем който може да се забележи при [2], е че авторите са направили оценка на точността чрез метод на крос-валидация, който пренебрегва времевия компонент в използваните рейтинги. Можем да твърдим, че по-правилен подход би бил със стандартно разделяне на множествата, където първите 70% от мачовете по време са заделени за извличане на закономерност, а последните 30% по време мачове се използват за оценка на точността на прогнозата.
Освен това, използваните MMR рейтинги са взети след края на всички мачове в данните. Използването на рейтинги след съответните мачове е възможно да доведе до нереалистична оценка за точността на прогноза при нови мачове, дори при правилно разбиване на множествата за трениране и тестване.
Като алтернатива на Логистичната Регресия, Conley et al. са използвали и метод на К най-близки съседи (KNN).
К най-близки съседи (K-Nearest Neighbhours)
A drawback of the basic “majority voting” classification occurs when the class distribution is skewed.
Класическия метод на най-близките съседи е непараметричен подход, при който ново наблюдение бива класифицирано като най-често срещания клас сред К на брой най-близки елементи, според някаква метрика \(\rho(x_1, x_2)\) дефинирана върху пространството от независими променливи \(\mathfrak{X}\) (най-често Евклидова).
По-точно, нека \(D:= (\overrightarrow{X_1}, Y_1), (\overrightarrow{X_2}, Y_2), ..., (\overrightarrow{X_n}, Y_n)\) са двойки наблюдения от независими променливи \(X_i\) и отклици \(Y_i\) (множество за трениране на модела). Ако дефинираме метрика \(\rho:\mathfrak{X} \times \mathfrak{X} \to \mathbb{R}\). По този начин, за ново наблюдение \((X, Y)\), можем да конструираме наредба \(X_1 \le X_2 \le ... \le X_n\) по такъв начин, че \(\rho(X, X_1) \le \rho(X, X_2) \le ... \le \rho(X, X_n)\). Така, за избран от нас хиперпараметър \(k\), можем да изберем множество \(D_k\) с първите \(k\) на брой елемента от наредбата и да вземем най-често срещания сред тяк клас за съответните отклици \(Y_1, ..., Y_k\).
\[ \hat{Y} = \underset{c}{argmax}\sum_{(x_i, y_i) \in D_k}I(c = y_i) \]
Изборът на \(k\) може да се направи чрез, примерно метод на крос валидация, като се изпробват различни стойности за \(k\) и се избере съответната, даваща най-висока точност на прогноза.
Предложената модификация от Perry&Conley[1] e, чрез добавяне на тегла \(w_i\) върху елементите от множеството за тренировка, така че
\[ \hat{Y} = \underset{c}{argmax}\sum_{(x_i, y_i) \in D_k}w_i \times I(c = y_i) \]
където теглата \(w_i\) са дефинирани по следния начин
\[ w_i := (\frac{\sum_{i=1}^{226}{AND(q_j, x_j^{(i)})}}{N'})^d \]
В горната дефиниция на тегло, \(x^{(i)}\) e вектора с избрани герои за i-тата игра от множеството за тренировка, \(N'\) e броя на герои във вектора за прогноза, а \(d\) е скалиращ полиномиален фактор, имащ ефект върху това колко акцент искаме да вкараме върху подобността на двата вектора от избрани герои. При голямо \(d\) засилваме ефекта на подобност на двата избора герои и съответно повече акцент върху колективния ефект на избора герои, докато при по-малко \(d\) се акцентира повече върху индивидуалния ефект на всеки герой. Индексирането се случва спрямо броя на различните герои, които могат да участват. Цялата функция се нормализира върху интервала \([0, 1]\).
Пробвайки различни стойности за степента \(d\), най-добра точност се постига за d = 4, като избора е направен чрез метод на крос валидация с 2 разбивания и размер на извадката - 20,000. Относно размера на множеството за трениране, след 10,000 наблюдения има малък растеж в точността на прогнозата, като максималната точност върху съответния набор от данни е около 70%.
Огромен проблем при съответния подход е времето отнемащо за оценка на точността на прогнозиране. Върху данните предоставени от Conley et al. [1], на алгоритъма на най-близките съседи му се наложиха повече от 24 часа за смятане на точността за различните стойности на \(d\).
Повтаряйки съответния модел за данните предоставени от Kaggle, получаваме следната графика за първите стойности на \(d\)
Виждаме, че точността на модела не се вдига над 0.56 при данни с по-балансирано съотношение на победи и загуби между двата отбора.
Невронни мрежи за класификация (TODO: cite wikipedia)
Един подход използван от Yang et al. [2], Chen et al. [3], Hanke et Chaimowicz [4] e модела на Невронната Мрежа. Невронната мрежа може да се разгледа като насочен ацикличен граф, имащ следната структура
Неврон (връх j в графа)
Невроните са върховете в ацикличния граф, които могат да се разгледат като функции приемащи вход p_j(t) от върховете родители в даден момент t. Притежават следните характеристики
- състояние \(a_j(t)\) в даден момент \(t\)
- активираща функция \(f\) изчисляваща състоянието на в нов момент \(t + 1\) приемайки предходното състояние \(a_j(t)\) и входът от предходните състояния \(p_j(t)\) така че \(a_j(t+1) = f(a_j(t), p_j(t))\). \(f\) най-често бива сигмоид.
- Изходна функция \(o_{j}(t)=f_{\text{out}}(a_{j}(t))\)
Входът за определен неврон \(p_j(t)\) най-често бива линейна комбинация на изходите от предходните неврони (върхове)
\[ p_j(t) = \sum_i{}o_i(t)w_{ij} \] Така моделът на невронната мрежа се свежда до намиране на теглата \(w_{ij}\) за всеки връх (неврон), като това може да се случи с минимизиране на някаква целева функция между изходите на невронната мрежа и истинските стойности на изхода \(y\).
Прилагайки модела на невронна мрежа върху данните от Kaggle получаваме 0.57 точност, върху множеството отделено за проверка, докато върху данните представени от Yan et al. [2], получаваме 0.6047, което леко надвишава точността произведена от прогнозирането с Логистична Регресия.
Модели върху данни от реално време
При събраните данни, притежаме информация за събраното злато и натрупания опит от играчите за всяка една минута от съответните партии. Един подход използван в [2] за трениране на прогнозиране върху данни от реално време, е отново да напаснем логистична регресия, но този път върху характеристики като злато, опит и убийства събрани върху интервали от пет минути. Нека първо въведем следните функции
\[ G(i, t, T) := \text{Златото на i-тия играч от отбор T в минута t}\\ L(i, t, T) := \text{Брой нокаутиращи удари на i-тия играч от отбор T в минута t} \]
\[ P(Y = 1|t=j; \overrightarrow{\beta}) = \frac{1}{1 + exp({-(\beta_0 + \sum_{i=j-6}^{j-1}\beta_ix_i+\sum_{i=j-6}^{j-1}\beta_i'x_i')}}, \text{за j=6, ..., T} \] където \(x_i\) e средната разлика в събраното злато между двата отбора в i-тата минута, а \(x_i'\) е средната разлика довършващи удари между двата отбора в i-тата минута, т.е.
\[ x_i := \frac{1}{5}\sum_{j=1}^5[G(j, i, \text{Сияние}) - G(j, i, \text{Мраколес})]\\ x_i' := \frac{1}{5}\sum_{j=1}^5[L(j, i, \text{Сияние}) - L(j, i, \text{Мраколес})]\\ \] Независимите променливи злато и финализиращи удари са избрани от общо 3, заедно с натрупан опит, като съответните са дали най-добра крива на прогнозата по време.
Виждаме, че кривата на точността започва силно да се дестабилизира след 75-тата минута, поради малкия брой мачове които имаме с дължина над 75 минути.
Освен Логистичната Регресия, друг подход разгледан в [1] e изграждане на Марковска Верига.
Дискретна Марковска Верига от първи ред
Дискретна Марковска Верига от първи ред е редица от дискретни случайни величини (случаен процес) \(\{X_t\}_{t\in \mathbb{N}}\), притежаваща Марковското свойство
\[ P(X_{t+1}|X_1=x_1, X_2=x_2, ..., X_t=x_t) = P(X_{t+1}|X_t=x_t) \] Тоест, вероятността за преминаване от едно състояние в друго, зависи единствено от текущото състояние в момента \(t\). По този начин, Марковската верига може да се зададе чрез стохастична матрица (матрица на преходите) \(P_{\{ij\}}\), където \(p_{ij}\) е вероятността да се премине от състояние \(i\) в състояние \(j\), както и от някакво начално разпределение \(\pi_0\) задаващо вероятностите за за влизане в различните състояния от стойностите на случайните величини на процеса. Марковската верига най-често може да се визуализира като насочен граф (фигура хх).
В нашия случай, за да възпроизведем резултатите, взехме средната разлика в златото между отборите по време и дискретизирахме стойностите в 8 отделни клетки за да конструираме пространството на състоянията. Дискретизацията изградихме чрез емпиричните квантили на златото.
Итерирайки по време и броейки честотата на смяна на състоянията на златото (оценка по метод на максимално правдоподобие) за побеждаващия отбор и за губещия отбор, получихме следните две преходни матрици.
Ако искаме да направим прогноза с Марковската Верига във време t, използваме формулата на Бейс \(P(Y = r | D)\), където Y - е бернулевата случайна величина описваща победа или загуба, а \(D = \{x_{t-5}, ..., x_{t-1}\}\) е множеството от средните разлики в златото между двата отбора за предходните 5 минути.
Така получаваме
\[ P(Y = r | D) = \frac{P(D|Y = r)P(Y = r)}{P(D)} = \frac{\prod_{i = 1}^5{P(x_{t-i}|Y = r)}P(Y = r)}{P(D|Y = 1)P(Y = 1) + P(D|Y = 1)P(Y = 1)} \]
В основата на горната формула стои траекторията на движение \(P(D|Y = r)\) за \(r \in \{0, 1\}\), тоест при съответно победа и загуба за съответния отбор който ще прогнозираме. За априорната вероятност \(P(Y=r)\) бихме могли да използваме и вероятността от прогноза върху данни от преди самото започване на мач (Предварителна Прогноза).
Отново, разбивайки множеството на такова за извличане на закономерности и такова за оценка на точността на прогнозиране, получаваме следните точности по време.
Виждаме, че Марковската Верига има значително по-добра прогноза в първите 25 минути, след което Логистичната Регресия повежда като точност.
Точността която получаваме съвсем не отговаря на тази предоставена във Yang et al.[2], но пък затова е върху множество от мачове с дължина на някои от тях до 80 минути, а не само до 40 минути.
Взимайки по-къси мачове (с продължителност 40 минути), успяваме да възпроизведем и даже получим по-висока точност до близо 40-тата минута, като между 25-тата и 30-тата минута, точността е над 90%.
Интуитивно това може да се обясни с това, че при по-късите игри има силен моментум за побеждаващия отбор, който да даде по-добър тренд за движение по състоянията на Марковската Верига. След 40-тата минута, мачовете са далеч по-оспорвани, а и в далеч по-малка наличност за извличане на закономерности. Като модификация на подхода предложен във [2], след известно експериментиране, сме направили дискретизация на златото не на 24 или 8, а на 60 клетки. Съответната дискретизация е дала и горепосочената точност.
Модели за препоръчване на избор на герой
Както споменахме в началото, преди започването на всяка партия, всеки от отборите трябва да избере героите с които да участва в съответния мач. Съществуват няколко начина по които може да се избират героите в една игра. Един от начините на избор на герои (наричан още драфт), който ще разгледаме е следния - в първия отбор се избира герой, след това във втория отбор се избират два героя, последвано от същата бройка за първия отбор и така нататък. Накрая втория отбор избира един герой. Поради самото редуване и уникалните свойства на всеки герой, самия драфт може да се разгледа като комбинаторна игра, при която двата отбора надиграват и контрират изборите си на герои. Пример за това би бил, че докато героя Медуза е силен срещу Върколака, нейния поглед не успява да вкамени героя Урса (Мечколака).
Една методология за най-добър избор на герои (препоръчване на герои) представена от [4] е чрез търсене в дърво по метод на Монте Карло.
Търсене в дърво по метод на Монте Карло
Дефинирайки избора на герои като комбинаторна игра с два играча (в този случай съответните отбори), имаме пространство от състояния на играта \(S \subset \mathbb{Z}^{113}\) - N-мерен вектор описващ избраните герои със съответни елементи \(s_i\in S\): \[ s_i = \begin{cases} 1,& \text{ако герой i участва в отбор Сияние} \\ -1, & \text{ако герой i участва в отбор Мраколес} \\ 0, & \text{в противен случай} \end{cases} \] Началното състояние разбира се е \(s_0=0^N\), без избор на герои до този момент, а крайните състояния \(S_T \subset S\) са вектори имащи точно пет пъти 1 и пет пъти -1 за изборите на героите от всеки отбор. Също така имаме множество от възможни действия (избори на герои по ред) в комбинаторната игра - \(А\), предопределено от функция \(\rho : S \to \{Сияние, Мраколес\}\) задаваща кой е на ред според съответното състояние на комбинаторната игра. Функцията \(f:S \times X \to S\) променя състоянията на играта според съответно състояние и действие, докато функцията на награда \(R: S \to \mathbb{R}^2\) задава двумерен вектор с възнаграждението от състояние, съответно за двата отбора. Възнаграждението има смисъл единствено за крайни състояния, като наградата бихме могли да оценим посредством прогноза за победа със соътветната комбинация герои посредством някои от моделите за предварителна прогноза с драфт описани по-горе.
Един вариант за намиране на оптимален път (такъв водещ до максимална печалба) е на всеки ред за избор на герой (състояние), да обходим цялото дърво надолу до листата, търсейки финално състояние което максимизира печалбата на текущия играч от избора и минимизиращо печалбата на противниковия отбор (Минимакс алгоритъм). Поради огромния брой възможни разклонения на дървото и ограничените изчислителни ресурси които имаме, Chen et al. [4] предлагат обхождане на дървото по метод на Монте Карло. Методът се състои от следните 4 стъпки
- Избор на съсед по дървото (действие) - При тази стъпка, алгоритъма избира следващ ход (съсед от текущия корен), при положение, че не е стигнал до листо и играта не е вече във финално състояние. За избора се използва информацията която имаме за наградата \(w\) която получаваме при съответните избори или някаква по-сложна полица (закон за избор на действие), примерно Полица на Доверителна горна граница (Upper Confidence Bound),
\[ \pi_{UCB_1}(s) := argmax_a\{\bar{w} + c\sqrt{\frac{\log n(s)}{n(s, a)}}\}, \] където s e текущото състоянието, а е възможно действие което да се вземе (избор на герой), \(\bar{w}\) e средната награда при взимане на действие \(a\) от \(s\), \(n(s, a)\) е броя пъти а е обходено през \(s\), a \(n(s)\) броя пъти минаване през \(s\) от различните симулации. В горната формула, \(c\) е регуларизираща константа (хипер параметър), това колко тежест да вложим в бройката на обходи на съответното състояние и действие.
Обхождане на дървото и симулация - При тази стъпка, алгоритъма обхожда дървото (симулира действия), като избора по който симулира следващ ход е на базата на дисретно равномерно разпределение. Действието се повтаря рекурсивно до достигане на финално състояние (листо в дървото), при което се изчислява наградата R(s) за съответното финално състояние \(s \in S_T\)
Oбратно разпространение на наградата (Backpropagation) - Наградата се връща нагоре по дървото, докато стигне корена (текущото състояние на комбинаторната игра), като по пътя нагоре във всеки връх се обновява информация с различни статистики като средна награда при поемане по този връх, брой обхождания, т.н.т.
Горната симулация продължава докато има достатъчно ресурси или време за да се прави това.